package com.demo.algorithm.bfs03;

import javax.xml.soap.Node;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

/**
 * Description: BFS算法套路模板
 * BFS问题的本质就是让你在⼀幅「图」中找到从起点 start 到终点 target 的最近距离。
 *
 * @Date: 2021/6/3 22:56
 * @Author: zsyoung@qq.com
 */
public class BFSTemplate {
    int BFS(Node start,Node target){
        Queue<Node> q = new LinkedList<>(); //核心数据结构
        Set<Node> visited = new HashSet<>(); //防止走回头路

        q.offer(start); //将起点加入队列
        visited.add(start);
        int step = 0; //记录扩散的步数

        while (!q.isEmpty()){
            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                Node cur = q.poll();
                /*划重点：这里判断是否到达终点*/
                if (cur == target){
                    return step;
                }
                /*将 cur 相邻的节点加入队列，cur.adj() 泛指 cur 相邻的节点，⽐如说⼆维数组中， cur 上下左右四⾯的位置就是相邻节点；*/
//                for(Node x:  cur.adj()){
//                    if (!visited.contains(x)){
//                        q.offer(x);
//                        visited.add(x);
//                    }
//                }
                /*划重点：步数更新在这里*/
                step++;
            }
        }
        return step;
    }

}
